1. Field of the Invention
This invention relates to the field of computer software. More specifically, the invention relates to a method and apparatus for structuring, storing and retrieving data in databases in a way that improves data management and retrieval.
2. Description of the Related Art
Relational data refers to data where entities are each associated with a set of data elements that are interrelated. For example, a catalog item (the entity) may be associated with a set of attributes (e.g., name, color, manufacturer name, description, etc.). A collection of items forms a database, or a product catalog in this example. The collection of items, in its simplest form, may be stored in a flat file where, for example, lines represent items, also referred to as records, in the catalog and each column represents a data field, or attribute. Modem relational databases use relational database management systems (RDBMS) to store and retrieve data. Modern relational database management systems employ sophisticated data storage and management and have communication means to exchange data with clients. For example, to allow easy access to data records, modern database management systems have the capability to partition the storage media into data pages and index the records into separate indices, which serve as direct pointers to the location of records. Modem database management systems also have the capability to simultaneously communicate with multiple clients through network sockets.
However, relational database management systems use an internal table representation that preserves some aspects of a flat file representation. For example, if a set of records is associated with a given attribute, a table representing all records must contain a field for that attribute. For all of the records that are not associated with that attribute, the value of the field is left empty. When items are retrieved from a single table, the database management system traverses the records in the table, one by one, to retrieve the records, or parts thereof, that fulfill a certain test condition. It is clear that storing and retrieving information from databases that use the single table approach is far from an optimal approach in terms of minimizing the storage space and the computation required for searching and retrieving data.
Modem database management systems provide multiple approaches, such as data indexing, to improve data storage and retrieval. However, with the constantly increasing amount of data and the need for conducting ever more sophisticated and complicated searches on the data, existing computation power may sometimes be unable to keep up with the demands of database processing.
The present invention discloses a data structure and method for storing, managing, and retrieving data from databases that optimizes the amount of storage space and minimizes the amount of computation needed to perform sophisticated searches.